import java.util.PriorityQueue;

/*
 * @lc app=leetcode.cn id=786 lang=java
 *
 * [786] 第 K 个最小的素数分数
 */

// @lc code=start
class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        //根据[堆内元素多少]和[当前计算值与堆顶元素的大小关系]决定入堆行为
        //堆内元素不足k个,直接将二元组入堆
        //若堆内元素已达k个,根据[当前计算值arr[i]/arr[j]]与堆顶元素[peek[0]/peek[1]]的大小关系
        //计算值比堆顶元素大,当前元素不可能是第k小的值.
        //计算值比堆顶元素小,堆顶元素不可能是第k小的值,使用当前值置换堆顶元素
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b) ->Double.compare(b[0]*1.0/b[1], a[0]*1.0/a[1]));
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                double t = arr[i] * 1.0 / arr[j];
                if(q.size() < k || t < q.peek()[0] * 1.0 / q.peek()[1]){
                    if(q.size() == k){
                        q.poll();
                    }
                    q.add(new int[]{arr[i], arr[j]});

                }
            }
        }
        return q.poll();
    }
}
// @lc code=end

